/*
 * @Author: lei
 * @Description: 冒泡排序示例
 * @FilePath: /code/bubblesort.cc
 */
#include <iostream>
#include <vector>
using namespace std;
// 一边比较一边向后两两交换，将最大值 / 最小值冒泡到最后一位；
// 经过优化的写法：使用一个变量记录当前轮次的比较是否发生过交换，如果没有发生交换表示已经有序，不再继续排序；
// 进一步优化的写法：除了使用变量记录当前轮次是否发生交换外，再使用一个变量记录上次发生交换的位置，下一轮排序时到达上次交换的位置就停止比较。

// g++ -o bubblesort bubblesort.cc -std=c++11
void BubbleSort1(vector<int>& v) {
  int len = v.size();
  for (int i = 0; i < len; i++) {
    for (int j = 1; j < len - i; j++) {
      if (v[j - 1] > v[j]) swap(v[j - 1], v[j]);
    }
  }
}
// 用一个flag布尔变量标记上一轮排序是否发生了交换
void BubbleSort2(vector<int>& v) {
  int len = v.size();
  bool flag;
  for (int i = 0; i < len; i++) {
    flag = false;
    for (int j = 1; j < len - i; j++) {
      if (v[j - 1] > v[j]) {
        swap(v[j - 1], v[j]);
        flag = true;
      }
    }
    if (!flag) break;
  }
}
// 找出最后一次交换的下标，优化内层for循环的次数
// [0,unsort_last_idx]区间为未排序区间
// [unsort_last_idx,v.size()-1]为有序区间
void BubbleSort3(vector<int>& v) {
  int len = v.size();
  int unsort_last_idx = len - 1;
  bool flag;
  int last_swap_idx = -1;
  for (int i = 0; i < len; i++) {
    flag = false;
    for (int j = 1; j < unsort_last_idx; j++) {
      if (v[j - 1] > v[j]) {
        swap(v[j - 1], v[j]);
        last_swap_idx = j;
        flag = true;
      }
    }
    if (!flag) break;
    unsort_last_idx = last_swap_idx;
  }
}
int main() {
  vector<int> v{1, 8, 3, 89, 0, -342, 90, -87, 987};
  for (auto& t : v) cout << t << " ";
  cout << endl;
  // BubbleSort1(v);
  // BubbleSort2(v);
  BubbleSort3(v);
  for (auto& t : v) cout << t << " ";
  cout << endl;
  return 0;
}